package link_list;

import link_list.node.SinglyListNode;

public class LinkedListTwoMerge {
    public static void main(String[] args) {
        SinglyListNode first = new SinglyListNode(1);
        first.next=new SinglyListNode(3);
        first.next.next=new SinglyListNode(5);


        SinglyListNode second = new SinglyListNode(2);
        second.next=new SinglyListNode(4);
        second.next.next=new SinglyListNode(6);
        SinglyListNode result = merge2(first,second);
        while (result !=null){
            System.out.print(result.val);
            result = result.next;
        }

    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public static  SinglyListNode merge (SinglyListNode pHead1, SinglyListNode pHead2) {
        if (pHead2 == null) {
            return pHead1;
        }
        if (pHead1 == null) {
            return pHead2;
        }
        SinglyListNode curNode=null;

        if (pHead1.val > pHead2.val) {
            curNode=merge(pHead1, pHead2.next);
            pHead2.next=curNode;
            return pHead2;
        } else {
            curNode=merge(pHead1.next, pHead2);
            pHead1.next=curNode;
            return pHead1;
        }
    }
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param pHead1 ListNode类
         * @param pHead2 ListNode类
         * @return ListNode类
         */
        public static SinglyListNode merge2 (SinglyListNode pHead1, SinglyListNode pHead2) {
            if (pHead1 == null && pHead2 == null) {
                return null;
            }
            if (pHead2 == null) {
                return pHead1;
            }
            if (pHead1 == null) {
                return pHead2;
            }
            // write code here
            SinglyListNode newHead = null;
            SinglyListNode curNode = null;

            if (pHead1.val > pHead2.val) {
                newHead = pHead2;
                curNode = newHead;
                pHead2 = pHead2.next;
            } else {
                newHead = pHead1;
                curNode = newHead;
                pHead1 = pHead1.next;
            }

            while (true) {
                if (pHead2 == null) {
                    curNode.next = pHead1;
                    break;
                }
                if (pHead1 == null) {
                    curNode.next = pHead2;
                    break;
                }
                if (pHead1.val > pHead2.val) {
                    curNode.next = pHead2;
                    curNode = curNode.next;
                    pHead2 = pHead2.next;
                } else {
                    curNode.next = pHead1;
                    curNode = curNode.next;
                    pHead1 = pHead1.next;
                }
            }
            return newHead;
        }

}
